package com.zjsru.plan2024.oneday;

/**
 * 494. 目标和
 * @Author: cookLee
 * @Date: 2024-06-30
 */
public class FindTargetSumWays {

    /**
     * 主
     * \
     * 输入：nums = [1,1,1,1,1], target = 3
     * 输出：5
     * 解释：一共有 5 种方法让最终目标和为 3 。
     * -1 + 1 + 1 + 1 + 1 = 3
     * +1 - 1 + 1 + 1 + 1 = 3
     * +1 + 1 - 1 + 1 + 1 = 3
     * +1 + 1 + 1 - 1 + 1 = 3
     * +1 + 1 + 1 + 1 - 1 = 3
     * \
     * 输入：nums = [1], target = 1
     * 输出：1
     * \
     * @param args args
     */
    public static void main(String[] args) {
        FindTargetSumWays findTargetSumWays = new FindTargetSumWays();
        int[] nums = new int[]{1,1,1,1,1};
        int target = 3;
        System.out.println(findTargetSumWays.findTargetSumWays(nums, target));
    }

    /**
     * 计数
     */
    private Integer count = 0;

    /**
     * 查找目标总和方式:递归
     *
     * @param nums   nums
     * @param target 目标
     * @return int
     */
    public int findTargetSumWays(int[] nums, int target) {
        this.helper(nums,target,0,0);
        return count;
    }

    /**
     * 帮手
     * 递归助手
     *
     * @param nums   nums
     * @param target 目标
     * @param index  索引
     * @param sum    总金额
     */
    private void helper(int[] nums, int target, int index, int sum) {
        if (index == nums.length) {
            if (sum == target) {
                count++;
            }
        } else {
            //正数
            this.helper(nums, target, index + 1, sum + nums[index]);
            //负数
            this.helper(nums, target, index + 1, sum - nums[index]);
        }
    }

}
